# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 解法1：生成完全顺序列表
# class Solution(object):
#     def recoverTree(self, root):
#         """
#         :type root: TreeNode
#         :rtype: None Do not return anything, modify root in-place instead.
#         """
#         val_list = [-pow(2, 31) - 1]
#
#         def ergodic_1(node):
#             if node:
#                 ergodic_1(node.left)
#                 val_list.append(node.val)
#                 ergodic_1(node.right)
#
#         ergodic_1(root)
#
#         val_list.append(pow(2, 31))
#         left_flag = False
#         for i in range(len(val_list) - 1):
#             if val_list[i] > val_list[i + 1]:
#                 if not left_flag:
#                     left_val = val_list[i]
#                     right_val = val_list[i + 1]
#                     left_flag = True
#                 else:
#                     right_val = val_list[i + 1]
#
#         def ergodic_2(node):
#             if node:
#                 if node.val == left_val:
#                     node.val = right_val
#                 else:
#                     if node.val == right_val:
#                         node.val = left_val
#                 ergodic_2(node.left)
#                 ergodic_2(node.right)
#
#         ergodic_2(root)

# 解法2：生成只包含两个元素的数组
# class Solution(object):
#     def recoverTree(self, root):
#         """
#         :type root: TreeNode
#         :rtype: None Do not return anything, modify root in-place instead.
#         """
#         val_list = [-pow(2, 31) - 1, 0]
#         wrong_list = [-pow(2, 31) - 1, 0]
#         flag = [0]
#         count = [1]
#
#         def ergodic_1(node):
#             if node:
#                 ergodic_1(node.left)
#                 val_list[count[0] % 2] = node.val
#                 if val_list[count[0] % 2] < val_list[(count[0] + 1) % 2]:
#                     if flag[0] == 0:
#                         wrong_list[1] = val_list[count[0] % 2]
#                         wrong_list[0] = val_list[(count[0] + 1) % 2]
#                         flag[0] += 1
#                     else:
#                         wrong_list[1] = val_list[count[0] % 2]
#                 count[0] += 1
#                 ergodic_1(node.right)
#
#         ergodic_1(root)
#         left_val = wrong_list[0]
#         right_val = wrong_list[1]
#
#         def ergodic_2(node):
#             if node:
#                 if node.val == left_val:
#                     node.val = right_val
#                 else:
#                     if node.val == right_val:
#                         node.val = left_val
#                 ergodic_2(node.left)
#                 ergodic_2(node.right)
#
#         ergodic_2(root)


# 解法3：Morris循环
class Solution(object):
    def recoverTree(self, root):
        pred = None
        y = None
        while root:
            if root.left:
                predecessor = root.left
                while predecessor.right and predecessor.right != root:
                    predecessor = predecessor.right
                if not predecessor.right:
                    predecessor.right = root
                    root = root.left
                else:
                    predecessor.right = None
                    if not pred:
                        pred = root
                    else:
                        if root.val < pred.val:
                            if not y:
                                x = root
                                y = pred
                            else:
                                x = root
                    root = root.right
            else:
                if not pred:
                    pred = root
                else:
                    if root.val < pred.val:
                        if not y:
                            x = root
                            y = pred
                        else:
                            x = root
                root = root.right
        temp = x.val
        x.val = y.val
        y.val = temp